Information security is an important aspect of providing a storage service. One of the ways in which stored information is secured is by using client-side encryption. In client-side encryption, the client computer system encrypts information to be stored using a cryptographic key, and transmits the encrypted information to the storage service. The storage service retains the encrypted information in encrypted form. In general, the unencrypted information is not accessible to the storage service. The client computer system can recover the information by retrieving the encrypted information from the storage service, and decrypting the encrypted information with the cryptographic key.
From time to time, it may be desirable or necessary to change the cryptographic key with which the information is secured. The process of changing the cryptographic key and updating the corresponding encrypted information is called key rotation. The client may perform key rotation by retrieving the encrypted information from the storage service, decrypting the encrypted information with an old cryptographic key, re-encrypting the decrypted information with a new cryptographic key, and transmitting the re-encrypted information to the storage service. As the amount of encrypted data stored on the storage service increases, key rotation becomes a more difficult and costly process. However, more frequent key rotation may also contribute to increased data security. Therefore, improving the ability of the client computer system to perform key rotation is an important problem.